﻿/*
菲波那契数 
Time Limit:1000MS  Memory Limit:32768K

Description:
菲波那契(fibonacci)数（简称菲氏数）定义为：
   f(0) = 0;
   f(1) = 1;
   f(n) = f(n-1) + f(n-2).     n>1的整数
如果写出菲氏数列，则应该是：
   0 1 1 2 3 5 8 13 21 34 ...
如果求其第6项，则应为8。
求第n项菲氏数。 

Input:
输入数据含有不多于50个的正整数n（0≤n≤46）。 
Output:
对于每个n，计算其第n项菲氏数，每个结果应占单独一行。 
Sample Input:
6 10
Sample Output:
8
55
*/
#include <iostream>
#include <vector>
#include <iterator>
using namespace std;

int main()
{
	unsigned v_size=51U;
	vector<unsigned> v;
	v.reserve(v_size);
	unsigned maximum=0U;
	for (unsigned n; cin>>n; v.push_back(n))
		if(maximum<n)
			maximum=n;
	vector<unsigned long> fibs;
	fibs.reserve(maximum+1);
	fibs.push_back(0);
	fibs.push_back(1);
	fibs.push_back(1);
	
	unsigned f1=1, f2=1;
	for (unsigned i=2; i<=maximum; ++i)
	{
		unsigned tmp=f2;
		f2=f1+f2;
		f1=tmp;
		fibs.push_back(f2);
	}

	for (vector<unsigned>::iterator it=v.begin(); it!=v.end(); ++it)
	{
		cout<<fibs.at(*it)<<endl;
	}
//	copy(fibs.begin(), fibs.end(), ostream_iterator<unsigned long>(cout, " "));

		
	return EXIT_SUCCESS;
}